package com.leetcode.algorithm.y22.m07;

/**
 * 424. 替换后的最长重复字符
 * 
 * https://leetcode.cn/problems/longest-repeating-character-replacement/
 * 
 * @author jie.deng
 *
 */
class Question0424Solution01 {
	
	public int characterReplacement(String s, int k) {
		// Step 1: 定义需要维护的变量
		int maxLen = 0; // maxLen ：最长重复字符的长度
		int[] cntAr = new int[26];// cntAr表示在当前滑动窗口内A-Z字符出现的次数
		char ch = s.charAt(0);// ch表示当前滑动窗口内出现频次最高的字符
		int maxCnt = 1;// maxCnt表示当前滑动窗口内出现频次最高的那个字符的个数
		cntAr[s.charAt(0) - 'A']++;

		// Step 2: 定义窗口的首尾端 (left, right)， 然后滑动窗口
		int left = 0;
		for (int right = 1; right < s.length();) {
			if (maxCnt + k < right - left) {
				// Step 4: 需要改变左索引的情况：改变左索引前，更新需要维护的变量
				maxLen = Math.max(maxLen, maxCnt + k);
				char chL = s.charAt(left);
				cntAr[chL - 'A']--;
				if (chL == ch) {
					maxCnt--;
					for (int i = 0; i < 26; i++) {
						if (cntAr[i] > maxCnt) {
							maxCnt = cntAr[i];
							ch = (char)(i+'A');
						}
					}
				}
				left++;
			}

			// Step 4: 改变右索引
			char chR = s.charAt(right);
			cntAr[chR - 'A']++;
			if (chR == ch) {
				maxCnt++;
			} else {
				if (cntAr[chR - 'A'] > maxCnt) {
					maxCnt = cntAr[chR - 'A'];
					ch = chR;
				}
			}
			right++;
		}

		// Step 5: 返回答案
		if (s.length() - left > maxCnt + k) {
			// 最后一个元素不满足条件
			maxLen = Math.max(maxLen, s.length() - left - 1);
		} else {
			// 最后一个元素满足条件
			maxLen = Math.max(maxLen, s.length() - left);
		}
		return maxLen;
	}
    
}